#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;

//记忆化
class Solution {
public:
    int dfs(int n, int &zero, int& one, vector<int> & mem){
        if (n < 0){ 
            return 0;
        }
        if (n == 0){ 
            return 1;
        }
        if (mem[n] != -1){ 
            return mem[n];
        }
        return mem[n] = ((dfs(n - zero ,zero, one, mem)) + dfs(n - one, zero, one, mem)) % mod;
    }
    int countGoodStrings(int low, int high, int zero, int one) {
        int ans = 0;
        vector<int> mem(high + 1, -1);
        for (int i = low; i <= high; i++){ 
            ans =  (ans + dfs(i, zero, one, mem)) % mod;
        }
        return ans;
    }
};

//dp
const int mod = 1e9 + 7;
class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;
        //dp[i] = dp[i - zero] + dp[i - one];
        //防止越界
        int ans = 0;
        for (int i = 1; i <= high; i++){
            if (i >= zero)
                dp[i] = dp[i - zero];
            if (i >= one)
                dp[i] = ((dp[i] + dp[i - one]) % mod);
            if (i >= low)
                ans = (ans + dp[i]) % mod;

        }
        return ans;
    }
};